package com.mdnote.structure.sort;

import java.util.Arrays;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/8/26
 * @description 希尔排序
 */
public class ShellSort {

    /**
     * 希尔排序，交换方案
     * @param source 数组
     */
    public static void sortBySwap(int[] source) {
        int temp = 0;
        // 分组
        for (int gap = source.length / 2; gap > 0; gap /= 2) {
            // 从gap个元素开始遍历
            for (int i = gap; i < source.length; i++) {
                // 遍历分组后的各个元素，然后比较交换
                for (int j = i; j - gap >= 0; j -= gap) {
                    if (source[j - gap] > source[j]) {
                        temp = source[j - gap];
                        source[j - gap] = source[j];
                        source[j] = temp;
                    }
                }
            }
        }
    }

    public static void sortByMove(int[] source) {
        for (int gap = source.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < source.length; i++) {
                // 交换方案
                // 先保存当前的值
                int currentValue = source[i];
                // 获取上一个元素的所有
                int insertIndex = i - gap;
                // 交换
                while (insertIndex >= 0 && currentValue < source[insertIndex]) {
                    source[insertIndex + gap] = source[insertIndex];
                    insertIndex -= gap;
                }
                // 放入元素
                if (insertIndex + gap != i) {
                    source[insertIndex + gap] = currentValue;
                }
            }
        }
    }


    public static void main(String[] args) {
        int[] data = {6, 5, 4, 3, 2, 1};
//        sortBySwap(data);
        sortBySwap(data);
        System.out.println(Arrays.toString(data));

    }
}
